package com.mlh.greed;

import java.sql.Struct;

/**
 * @author 缪林辉
 * @date 2024/4/10 11:02
 * @DESCRIPTION
 */
// 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
// 数组中的每个元素代表你在该位置可以跳跃的最大长度。
// 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
// 输入：nums = [3,2,1,0,4]
// 输出：false
// 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
public class 跳跃游戏 {
    //问题可以转化为跳跃覆盖范围究竟可不可以覆盖到终点！
    //贪心思路：
    //每次选择跳到该跳范围内 能够跳到更远位置的位置（即增加最大覆盖范围）
    public boolean method1(int[] nums) {
        if(nums.length<=1){
            return true;
        }
        int site=0;
        while (site+nums[site]<nums.length-1){
            int max=0; //记录能跳到最远处
            int maxIndex=-1;//记录能跳到最远处所在的下标
            //选取该跳范围内能够跳到最远位置 的位置
            for (int i = 1; i <=nums[site]&&site+i<nums.length; i++) {
                if (site + i+nums[site + i] > max) {
                    max = site + i+nums[site + i];
                    maxIndex=site + i;
                }
            }
            //如果发现该跳范围内能够跳到最远位置还是在该跳范围内，那说明跳不出去了，返回false
            if(max<=site+nums[site]){
                return false;
            }
            site=maxIndex;
        }
        return true;
    }

    //代码随心录的代码
    //我和他的思路大致相同，但是他的思路还是更加简洁
    public boolean method2(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        //覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
        int coverRange = 0;
        //在覆盖范围内更新最大的覆盖范围
        for (int i = 0; i <= coverRange; i++) {
            coverRange = Math.max(coverRange, i + nums[i]);
            if (coverRange >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }

    //用覆盖范围理解
    //你跳到一处他的覆盖范围更广肯定比覆盖范围小的好
    //因为你比他有更多的选择，你已经包括他了
    public boolean practice(int[] nums) {
        int cover=nums[0];
        //start和end是一跳区间内的前后下标
        int start=0;
        int end=cover;
        boolean flag=true;
        while (flag&&cover<nums.length-1){
            flag=false;
            for (int i = start; i <=end; i++) {
                cover=Math.max(i+nums[i],cover);
                flag=true;
            }
            start=end+1;
            end=cover;
        }
        return cover<nums.length-1?false:true;
    }
}
